COMMENT ⊗   VALID 00019 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\init{
C00004 00003	\chapbegin{3}		% Here beginneth Chapter 3
C00005 00004	\sectionbegin[1]{Introduction}
C00009 00005	\sectionbegin[2]{Basic assumptions}
C00017 00006	\subsectionbegin[2.2]{Specifics: How the Assumptions Were Applied}
C00024 00007	\sectionbegin[3]{Design criteria}
C00028 00008	\sectionbegin[4]{Basic ideas}
C00033 00009	\lsectionbegin[5]2{Trace of System Performance:}{Explanations for Performance
C00036 00010	{\tracebegin
C00046 00011	\topinsert{\vskip 42pc \vfill		% Figure 6--1
C00049 00012	\sectionbegin[6]{The need for an information metric}
C00056 00013	\sectionbegin[7]{More sophisticated HOWs}
C00070 00014	\sectionbegin[8]{Special purpose responses}
C00076 00015	\sectionbegin[9]{Limitations}
C00086 00016	\subsectionbegin[9.3]{Lack of Ability to Represent Control Structures}
C00096 00017	\lsectionbegin[10]2{Trace of System Performance:}{Explanations for System Debugging}
C00107 00018	My\ therapy\ recommendation\ will\ be\ based\ on\ the\ following\eol
C00117 00019	\sectionbegin[11]{SUMMARY}
C00121 ENDMK
C⊗;
\init{
\input cmpdes
\input temacs
\def\draft{T}
\titlepage
\newpage
\setcount0 31
\parttitle{TEIRESIAS: META-LEVEL KNOWLEDGE IN KNOWLEDGE-BASED SYSTEMS}
}
\baselineskip 12pt
\chapbegin{3}		% Here beginneth Chapter 3
\chaptertitle{EXPLANATION}
\rjustline{\:B Explanation}
\tenpoint
\vskip 14pc

\epigraph{What do you mean?  What you have said so far leaves me
uncertain whether to trust or fear.}
\author{Sophocles}
\source{Oedipus the King, lines 88--90}
\epigraphend

\epigraph{``No, no! The adventures first,'' said the Gryphon in an impatient tone:
``explanations take such a dreadfully long time!''}
\author{Lewis Carroll}
\source{Alice's Adventures in Wonderland}
\epigraphend

\sectionbegin[1]{Introduction}
	The fundamental goal of an explanation facility is to enable a
program to display a comprehensible account of the motivation for all of
its actions.  This chapter explores steps taken toward this goal, examining
the extent to which ``all'' actions of a program can be explained.  It
considers what is required for a ``comprehensible'' account and offers a
framework in which to understand ``motivations'' for one particular system.

	The utility of an explanation facility should be clear.  Even for
an experienced programmer, the attempt to account for program behavior by
hand simulation is difficult for any sizable program.  It is often
difficult enough to discover how a program got to where it is.  Trying to
account for past behavior (\eg, function calls that have long since
exited) is often impossible because critical variables have been
overwritten.

	For consultation programs, in particular, the problem of
explanation is worse because they deal with an audience assumed to know
nothing about programming.  This requires a different standard of
comprehensibility, one defined in terms of the application domain rather
than the language of computation.  A naive user (\eg, a student) should
find the explanations educational; a more experienced user should find them
reassuring, employing them to satisfy himself that the conclusions the system has
reached are based on acceptable reasoning; while an expert should find them
useful in discovering gaps or errors in the knowledge base.  We describe
below how each of these objectives is accomplished.

	This chapter begins by outlining and discussing the plausibility of
the fundamental assumptions behind the techniques used in {\TEIRESIAS}.  This is
followed by several examples of the capabilities that have been developed
and a description of how they are achieved.  Finally, as a prelude to
knowledge acquisition, we end by exploring how {\TEIRESIAS} may be used to discover
the source of problems in the knowledge base.

\sectionskip
\sectionbegin[2]{Basic assumptions}
The techniques used in {\TEIRESIAS} for generating explanations are based on
a number of assumptions about the system being explained.  These
assumptions are reviewed here to help motivate what follows and to
characterize their range of applicability.


\subsectionbegin[2.1]{Generalities: Two Assumptions}
	We assume, first, that a recap of program actions can be an
effective explanation as long as the correct level of detail is chosen.
This assumption simplifies the task considerably, since it means that the
solution requires only the ability to record and play back a history of
events.  In particular, it rules out any need to simplify those events.

	But this assumption
is perhaps the source of greatest limitation as
well.  It is not obvious, for instance, that an appropriate level of detail can
always be found.  A large program with cooperating parallel processes might
prove sufficiently complex that it required a sophisticated interpretation and
simplification  to be  comprehensible.  Neither is it
obvious how this approach can  be applied to programs that are primarily\index{symbolic reasoning}
numeric.  With a program that does symbolic reasoning, recapping offers an
easily understood explanation.  But simply recapping the arithmetic involved in
determining parameters of a complex electrical network, for example, would
explain little of the reasoning involved and would teach little physics.
Understanding it requires a much higher level of sophistication: It assumes that
the viewer can interpret each numeric step in symbolic terms.  The lack of any
mechanism for either simplifying or reinterpreting computations means our
approach is basically a first order solution to the general problem of
explaining program behavior.

	If a simple recap is going to be effective, there must be several\index{level of detail}
constraints on the level of detail chosen.  It must be {\sl detailed enough}
that the operations it cites are comprehensible.  For example, if a chess
program were to explain a move with the justification that it ``picked the
best choice,'' the explanation would explain very little because it wouldn't
reveal what was involved in the operation of choosing.  Some explanation in
terms of alpha/beta search and evaluation functions might provide the
relevant information.

	The level must also be {\sl high enough} that the operations are meaningful
to the observer and that unnecessary detail is suppressed.  Describing the chess
program in terms of register-transfer operations, for instance, would lose any
sense of task specificity and introduce pointless detail.

	Finally, the explanation
must be {\sl complete enough} that the operations cited are
sufficient to account for all behavior.  Completeness
is easiest to achieve if the operations
are free of side effects and the system design is reasonably ``clean.'' If the
alpha/beta search used in the chess program had numerous subtle side effects, it
would be difficult to find a level of detail that could account for the side
effects without introducing other irrelevant information.

	The second major assumption is that there exists some framework for viewing the
program's actions that will allow them to be comprehensible to the
observer.  The likely validity of this assumption
depends on both the program's fundamental mechanisms and the level at which
these
are examined.  Consider a program that does medical diagnosis using a statistical
approach based on Bayes' Theorem.  It is difficult to imagine what explanation
of its actions the program could give if it were queried while computing
probabilities.  No matter what level of detail is chosen, the approach is not
(nor is it intended to be) an accurate model of the reasoning process typically
employed by physicians (see [Tversky74] for some experimental verification).  As
effective as these actions
may be, there is no easy way to interpret them  in
terms that will make them comprehensible to a physician unacquainted with the
program.

	With the current state of the art, then, the desire to have a program 
capable of explaining its actions strongly constrains the methodology chosen and the
control structure that can be used.  There do not yet appear to be general
principles for generating explanations of arbitrary control structures in the
way, for example, that an experienced programmer can read unfamiliar code and
then explain it to someone else.  As a result, the capability cannot now be
tacked on to an existing system.  To make the problem tractable, the desired
capabilities must be taken into account early in the system-design process.

\subsectionbegin[2.2]{Specifics: How the Assumptions Were Applied}
	The fundamental organization of the performance program described
earlier provides an environment in which both of these assumptions can be
satisfied.  The simple and/or goal-tree control structure and the 
domain-specific rules invoked in a {\sl modus ponens} mode offer a basis for
explanations that typically need little additional clarification.  The
invocation of a rule is taken as the fundamental action of the system.
This, along with the goal tree as a framework, accounts for enough of the
system's operation to make a recap of such actions an acceptable
explanation.  In terms of the constraints noted earlier, it is sufficiently
detailed---the actions performed by a rule in making a ``conclusion,'' for
instance, correspond closely enough to the normal connotation of this word
that no greater detail is necessary.  It is still at an abstract
enough level that the operations are meaningful.  Finally, it is generally
complete enough---there are typically no other mechanisms or sources of
information that the observer needs to know in order to understand how the
program reaches its conclusions.\ffnote{The hedging here arises because, on those
occasions when explanations produced by {\TEIRESIAS} are cryptic, it is often a result of
incompleteness of this sort.  There are, for instance, rules in the performance
program whose format and content have been influenced by the attempt to take
advantage of subtle aspects of the control structure (\eg, ordering the
clauses of a premise so that certain attributes are traced first).  
Since there is in the system no indication of which rules have
been so modified, the simple goal-tree model is incomplete is this respect.}

	The success of this technique relies to some extent on the claim
that the performance program's approach to its domain is sufficiently intuitive
that a summary of those actions is a reasonable basis for explanation.
While we have not yet attempted to prove the claim in any formal sense,
there are several factors that suggest its plausibility.

	First, the performance program
is dealing with a domain in which deduction, and
deduction in the face of uncertainty, is a primary task. The use of\index{production rules}
production rules seems therefore to be a natural way of expressing things
about the domain and the display of such rules should be comprehensible.\index{backward chaining}
Second, the use of such rules in a backward-chaining mode seems to be a
reasonably intuitive scheme.  {\sl Modus ponens} is a well-understood and
widely (if not explicitly) used mode of inference.  Thus, the general form
of the representation and the way it is employed should not be unfamiliar
to the average user.  More specifically, however, consider the source of
the rules.  They are supplied by human experts who were attempting to
formalize their own knowledge of the domain.  As such, the rules
embody accepted
patterns of human reasoning, implying that they should be relatively easy
to understand, especially for those familiar with the domain.  As such,
they  also attack the problem at what has been judged an appropriate
level of detail.  That is, they  embody the right size  ``chunks'' of
the problem to be comprehensible.\index{high-level language}

	Many of the capabilities of the current explanation system also
depend on the presence of a high-level language of the sort described in
chapter 2.  Extensive use is made of the stylized code and the small number of
classes of primitives found in this language.  This makes possible, in
particular,  dissection and interpretation of the rules, techniques which
form the
basis for many of {\TEIRESIAS}'s capabilities.

	We have referred several times to explanations that are
``comprehensible'' and ``complete,'' which raises the questions
Comprehensible to whom?  and  Complete enough for whom?  As indicated,
our efforts have been directed at users from the application domain.  It is
with respect to this audience that ``comprehensible'' and ``complete'' are
used, and it is with respect to their
conceptual level that appropriate explanations must be
produced.  While a different level would have to be chosen for a different
audience (\eg, experienced programmers), the criteria above remain valid if
the explanations are to be based on a recap of program actions.

\sectionskip
\sectionbegin[3]{Design criteria}
	There were three criteria central to the design of the explanation
facilities.

\listbegin
\numlistentry[1]{{\sl Accuracy}.  Above all else, the explanations generated had
to provide an accurate picture of what was going on in the performance
program.  This meant overcoming several temptations; in particular, the
desire to ``dress things up just a bit,'' to cover over some of the less
impressive (or less transparent) aspects of {\sc MYCIN}'s behavior.  If
the facilities were to be an effective debugging tool, they had to be
accurate.}

\numlistentry[2]{{\sl Comprehensibility}.  Since computer consultants are intended for use by a
nonprogramming audience, the explanations generated by {\TEIRESIAS} had to be
tailored accordingly.  This meant restrictions on content and vocabulary
and an emphasis on brevity.  This criterion
was the main source of the temptation to
gloss over parts of {\sc MYCIN}'s behavior, to avoid having to justify in
layman's terms the  decisions that were based on computational
considerations.\index{human engineering}}

\numlistentry[3]{{\sl Human engineering}.  Consideration was also given to a collection of
user-oriented factors like ease of use, power, and speed.}
\listend

	As might be expected, (1) and (2) occasionally conflict, in part because
the facilities are powerful enough to allow the user to examine aspects of
the performance program not normally intended for display.  As one example,
the first eight or nine questions of a consultation are generated as part
of the initialization phase of the program and hence use a few
nonstandard mechanisms.  Their external appearance is the same as those
generated by the standard method of backward chaining of rules, but the
user can (perhaps unwittingly) uncover some perplexing operations if he
explores this part of the process with the explanation facilities.  There
are good reasons for all of these operations, but it would take some
extended discussion to make them clear to a nonprogrammer.

	Wherever conflicts did arise, they were resolved using the design
goals in the order listed.  The facilities present an accurate picture of
system performance; they do so as comprehensibly as possible and attempt
to be fast and easy to use.

\sectionskip
\sectionbegin[4]{Basic ideas}
	The basic ideas behind the design of the explanation facilities can
be viewed in terms of the four steps discussed below.

\listbegin 
\numlistentry[1]{{\sl Determine the program operation that is to be viewed as
primitive.}  This gives the smallest unit of program behavior that can be
explained.  Examples further on will demonstrate that it is possible to
generate different degrees of abstraction, but the level chosen in this
step determines the level of maximum detail.  In our case, the invocation
of an individual rule was selected as the primitive operation.}

\numlistentry[2]{{\sl Augment the performance program code to leave
behind a record of behavior at this level of detail.}
The result is a complete trace of program behavior, a history of
performance. The relevant sections of the performance program's control
structure (\ie, the inference engine) were augmented in this way to write
a history of rule invocation attempts.}

\numlistentry[3]{{\sl Select a global framework in which that trace can be
understood.}  This framework is important especially where computationally naive
users are concerned.  The trace provides a record of behavior, but the
framework supplies a way of understanding that behavior.  Its selection is
thus a central task in the construction of the facilities.}

\listentpara
	The framework was readily supplied by the performance program's\index{goal tree}
control structure---the and/or goal tree offered a natural perspective in
which to view program behavior and its explanation.  The tracing task is\index{tree traversal}
structured in terms of tree traversal, and the user is offered a set of
commands designed around it.  The goal-tree view is of course specific to
this particular control structure, but analogous frameworks are possible
for other system designs.

\numlistentry[4]{{\sl Design a program that can provide the user with an
interpretation of the trace.}  The program should be capable of
systematic examination of the
trace and should use the framework chosen to provide an interpretation of
events recorded there.  A body of code to do this forms the explanation
program in {\TEIRESIAS} and enables the user to examine the behavior of the
performance program.  It interprets the trace in terms of the and/or
goal-tree framework and provides a set of commands that allows the user to
examine previous, current, or future (potential) behavior.}
\listend

\noindent
These ideas form the foundation for the basic set of explanation
capabilities.  They are illustrated below with a number of annotated
examples.

\sectionskip
\lsectionbegin[5]2{Trace of System Performance:}{Explanations for Performance
Validation}

\epigraph{Modern-day computers are amazing pieces of equipment, but most amazing
of all are the uncertain grounds on account of which we attach any validity to their
output.}
\author{E.\ Dijkstra, \etal}
\source{Structured Programming}
\epigraphend

\noindent
\index{reasoning chain}During a consultation, the performance
program takes the initiative,
asking questions of the user. If one of those questions seems
inappropriate, the user can interrupt and use {\TEIRESIAS}'s explanation
facilities to find out what's going on.  By examining the chain of
reasoning that prompted the question, he can find out if the reasoning was
motivated by plausible considerations.

\index{tree traversal}Since explanation is viewed in terms of traversal of the and/or
goal tree, the command set is designed accordingly.  The two basic commands
are ``why'' and ``how,'' corresponding to ascent and descent of the tree.  It
is the performance program's invocation of rules in a goal-directed fashion
that makes  tree traversal operations plausible interpretations of the
commands.

	Several annotated examples are given below, in this and subsequent
sections.  In each case, a single question from the consultation has been
extracted and the explanation facilities have been used to examine the reasoning
behind it.  Figure 3--1 shows the part of the reasoning tree  being
examined in the first example.

	In the trace below, computer output is in {\tt mixed upper and lower case
in this font}, user responses are in {\bf BOLDFACE CAPITALS}, while annotations
are indented in {\sl $\{$italics inside braces$\}$}.

\null
{\tracebegin
In\ light\ of\ the\ site\ from\ which\ the\ culture\ was\ obtained\ and\eol
the\ method\ of\ collection,\ do\ you\ feel\ that\ a\ significant\eol
number\ of\ ORGANISM-1\ were\ obtained?\eol
**\ {\bf WHY}\eol
[i.e.,\ Why\ is\ it\ important\ to\ determine\ whether\ a\ ORGANISM-1\eol
\ was\ observed\ in\ significant\ numbers?]\eol
\eol
1.0]\ This\ will\ aid\ in\ determining\ whether\ there\ is\eol
\ \ \ \ \ therapeutically\ significant\ disease\ associated\ with\eol
\ \ \ \ \ this\ occurrence\ of\ ORGANISM-1.\eol
\ \ \ \ \ It\ has\ already\ been\ established\ that\eol
\ [1.1]\ the\ method\ of\ collection\ is\ sterile,\eol
\ \ \ \ \ therefore,\ if:\ \eol
\ [1.2]\ the\ organism\ was\ observed\ in\ significant\ numbers,\ and\eol
\ [1.3]\ the\ site\ of\ the\ culture\ is\ not\ one\ of\ those\ which\ are\eol
\ \ \ \ \ \ \ normally\ sterile,\eol
\ \ \ \ \ then\eol
\ there\ is\ strongly\ suggestive\ evidence\ (.9)\ that\ there\ is\eol
\ therapeutically\ significant\ disease\ associated\ with\ this\eol
\ occurrence\ of\ the\ organism.\eol
\ [Also:\ there\ is\ strongly\ suggestive\ evidence\ (.8)\ that\ the\eol
\ \ organism\ is\ not\ a\ contaminant.]\eol
\ [RULE054]\eol
\traceend}

\scomm As Figure 3--1 shows, the issue of ``a significant number of organisms'' is
one subgoal, ``therapeutically significant disease'' is another at the next
level up, and rule 54 links them.  The ``reason'' for asking the original
question, then, is to invoke rule 54 to determine the higher subgoal, and
the answer to ``why'' is simply a display of the goals and the rule linking
them.

\commpara Considerable attention has been paid to making this as lucid a
display as possible.  First, since ``why'' has several other interpretations
and no more extensive natural language capabilities are available, the
question is expanded by {\TEIRESIAS} to indicate the sense in which it will
be answered.  The higher level goal is then presented, followed by the
rule.  The premises of the rule are divided into those already established
and those yet to be determined, using the template mechanism described in
chapter 2.  Finally, since rules may have multiple conclusions about
different attributes, the relevant conclusion is presented first and all
others follow.\ecomm

** {\bf WHY}\eol

\scomm Further sections of the reasoning chain can be examined by repeating
the command.\ecomm

{\tracebegin
[i.e.,\ Why\ is\ it\ important\ to\ find\ out\ whether\ there\ is\eol
\ therapeutically\ significant\ disease\ associated\ with\ this\eol
\ occurrence\ of\ ORGANISM-1?]\eol
\eol
[2.0]\ellipsis\ in\ order\ to\ find\ out\ a\ locus\ of\ infection\ in\ \eol
\ \ \ \ \ PATIENT-1.\ \ It\ has\ already\ been\ established\ that:\eol
\ [2.1]\ the\ number\ of\ days\ since\ the\ specimen\ for\ the\ culture\eol
\ \ \ \ \ \ \ was\ obtained\ is\ less\ than\ 7,\eol
\ \ \ \ \ therefore,\ if:\eol
\ [2.2]\ there\ is\ therapeutically\ significant\ disease\eol
\ \ \ \ \ \ \ associated\ with\ this\ occurrence\ of\ the\ organism\eol
\ \ \ \ \ then\eol
\ it\ is\ definite\ (1.0)\ that\ the\ site\ of\ the\ culture\ is\ a\eol
\ locus\ of\ infection\ in\ the\ patient.\eol
\ [RULE021]\eol
\eol
**\ {\bf WHY}\eol
[i.e.,\ Why\ is\ it\ important\ to\ determine\ a\ locus\ of\ infection\eol
\ in\ PATIENT-1?]\eol
\eol
[3.0]...in\ order\ to\ find\ out\ about\ an\ organism\ or\ class\ of\eol
\ \ \ \ \ organisms\ for\ which\ therapy\ should\ cover.\eol
\ \ \ \ \ It\ has\ already\ been\ established\ that:\eol
\ [3.1]\ the\ site\ of\ the\ culture\ is\ blood,\ and\eol
\ [3.2]\ the\ stain\ of\ the\ organism\ is\ grampos,\ and\eol
\ [3.3]\ the\ portal\ of\ entry\ of\ the\ organism\ is\ GI,\eol
\ \ \ \ \ therefore,\ if:\eol
\ [3.4]\ [A\ -\ abdomen\ is\ a\ locus\ of\ infection\ in\ the\ patient,\eol
\ \ \ \ \ or,\eol
\ \ \ \ \ \ \ \ B\ -\ pelvis\ is a locus of infection in the patient]\eol
\ \ \ \ \ then\eol
\ there\ is\ strongly\ suggestive\ evidence\ (.9)\ that\eol
\ enterobacteriaceae\ is\ a\ class\ of\ organisms\ for\ which\eol
\ therapy\ should\ cover.\eol
\ [RULE095]\eol
\eol
**\ {\bf HOW [3.0]}\eol
\traceend}

\scomm HOW can be used to climb ``down'' the reasoning chain and gives a picture
of all the ways any subgoal may be achieved.  In the examples demonstrating
its use, numbers following the command refer to the corresponding items
above (\eg, the {\tt [3.0]} above).\ecomm

{\tracebegin
[i.e.,\ How\ were\ you\ determining\ an\ organism\ or\ class\ of\eol
\ organisms\ for\ which\ therapy\ should\ cover?]\eol
\eol
[4.0]\ At\ that\ point\ RULE095\ was\ being\ used.\ \ In\ addition,\eol
\ [4.1]\ RULE162\ was\ used\ to\ conclude\ that\ bacteroides\ is\ an\eol
\ \ \ \ \ \ \ organism\ for\ which\ therapy\ should\ cover,\ and\eol
\ [4.2]\ RULE115\ will\ be\ tried\ later,\ as\ well.\eol
\traceend}

\scomm Once again the question is underspecified and is expanded by {\TEIRESIAS}.  Note
that the system can indicate reasoning chains previously followed, those
currently being examined, and those yet to be tried.  Each can be further
explored.\ecomm

{\tracebegin
** {\bf HOW [4.1]}\eol
[i.e.,\ How\ was\ RULE162\ used?]\eol
\eol
[5.0]\ \ It\ has\ already\ been\ established\ that:\eol
\ [5.1]\ the\ site\ of\ the\ culture\ is\ blood,\ and\eol
\ [5.2]\ the\ portal\ of\ entry\ of\ the\ organism\ is\ GI,\ and\eol
\ [5.3]\ the\ patient\ is\ a\ compromised\ host.\eol
\ \ \ \ \ \ \ Therefore,\eol
\ it\ is\ definite\ (1.0)\ that\ bacteroides\ is\ an\ organism\ for\eol
\ which\ therapy\ should\ cover.\eol
\ [RULE162]\eol
\eol
**\ {\bf\ HOW\ [4.2]}\eol
[i.e.\ How\ will\ RULE115\ be\ used?]\eol
\eol
\ If\ [6.0]\ brain-abscess\ is\ an\ infectious\ disease\ diagnosis\eol
\ \ \ \ \ \ \ \ \ \ for\ the\ patient,\eol
\ then\ \ \ \ \ there\ is\ weakly\ suggestive\ evidence\ (.2)\ that\eol
\ \ \ \ \ \ \ \ \ \ streptococcus-anaerobic\ is\ an\ organism\ for\ which\eol
\ \ \ \ \ \ \ \ \ \ therapy\ should\ cover.\eol
\ \ \ \ \ \ \ \ \ \ [RULE115]\eol
\traceend}

\sectionskip
\topinsert{\vskip 42pc \vfill		% Figure 6--1
\figtitle 6-1{Reasoning tree for the first set of explanation examples.}}

% .FULLPAGEFIG;
% .GROUP SKIP 4;
% .BOXFIG;
% 		  ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% 		  } what organisms }
% 		  } should therapy }
% 		  }     cover      }
% 		  α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 			  ↑
%         RULE162           } RULE095          RULE115
% 			  }
% 
% 
% 
% ⊂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂⊃
% }site =}  }gram =  }  }portal =}  }locus =}  }locus =}
% }blood }  }positive}  }GI tract}  }abdomen}  }pelvis }
% α%∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂$
% 					    ↑
% 					    } RULE021
% 					    }
% 
% 
% 			 ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃        ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% 			 }  num. days  }        } significant }
% 			 } less than 7 }        }   disease   }
% 			 α%∂∂∂∂∂∂∂∂∂∂∂∂∂$        α%∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 						      ↑
% 						      } RULE054
% 						      }
% 
% 
% 	      ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃  ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% 	      }  collection }  } significant }  }  nonsterile }
% 	      }   sterile   }  }   number    }  }    site     }
% 	      α%∂∂∂∂∂∂∂∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂∂∂∂∂∂∂$  α%∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% )  %1-- conjunction%A
% )) %1-- disjunction
% 
% .FIG(Reasoning tree for the first set of explanation examples,EXPLBOXES:);
% .ENDFIG;

\sectionbegin[6]{The need for an information metric}

\epigraph{[In an explanation] we must not carry reasoning too far back,
or the length
of our argument will cause obscurity; neither must we put in all the steps
that lead to our conclusion, or we shall waste words in saying what is
manifest.}
\author{Aristotle}
\epigraphend
\index{information metric}

\noindent
One problem anticipated in the use of the WHY command, and one that
is common to explanations in general, is the issue of an appropriate
level of sophistication and detail.  It is generally of little use to
discover that\index{level of detail}

\null
{\tracebegin
If:\ \ 1)\ The\ gram\ stain\ of\ the\ organism\ is\ grampos,\ and\eol
\ \ \ \ \ 2)\ The\ morphology\ of\ the\ organism\ is\ rod\eol
Then:\ \ It\ is\ definite\ (1.0)\ that\ the\ category\ of\ the\eol
\ \ \ \ \ \ \ organism\ is\ grampos-rods.\eol
\traceend}
\figtitle 3-2{RULE140.}

\noindent
Depending on the individual user, it might be best to display all steps in
a reasoning chain, to omit those that are definitional or trivial, or, for
the most sophisticated user, to display only the highlights.
This presumes that we have some idea of what
constitutes ``the details.'' In terms of the goal tree, it means knowing how
``far'' it is conceptually from one node to another, which is difficult since
this depends very much on the (constantly changing) state of the user's
knowledge.  It is also very important since the best explanations are those
based on a clear understanding of the extent of the user's comprehension.

        In a very rough analogy to information theory, we use -(log CF) to
provide this measure.  Definitional rules (with CF = 1.0) thus have no
information, while those with smaller CFs have progressively more.  This is
clearly imperfect.  It does not take into account the state of the user's
knowledge, and since CFs are not probabilities there is no formal
justification that -(log CF) is a meaningful number.  It's primary utility,
however, is as a ``dial'' with which the user can adjust the level of detail
in the explanations.  Absolute settings are less important than the ability
to make relative adjustments.

        The adjustment is made via an optional argument to the WHY command.
The entire ``distance'' from the current node to the top of the goal tree is
normalized to 10, and the argument following the WHY is taken as some
fraction of that distance.  Thus, rather than the multiple WHYs seen above,
the user might have asked ``WHY 4'':

% In light of the site from which the culture was obtained, and
% the method of collection, do you feel that a significant number
% of ORGANISM-1 were obtained?
% ** %3WHY 4%A
% [\ie, Why is it important to determine whether a significant
% number of ORGANISM-1 were obtained?]
% 
% We are trying to find out whether the organism has been
% observed in significant numbers, in order to determine an
% organism or class of organisms for which therapy should cover.
% .FIG(A `high-level' explanation,HILEVELEXPL:);
% .ENDFIG;CONTINUE;
\vskip 10pc
\figtitle 3-3{A ``high-level'' explanation.}

\noindent
Since the three steps in the chain shown in Figure 3--1
constitute roughly two-fifths of the
``distance'' to the top, they are compressed into a single answer.  This
command may be repeated as often as necessary, allowing the user to
follow the reasoning chain in step sizes of his own choosing.

        The user may occasionally choose a step size that is too big,
compressing too many steps into a single answer,  leaving him with an
incomprehensible explanation.  In this case he can invoke the EXPLAIN
command, which will cover the same starting and ending points in the
reasoning, but in more detail.  Thus, if the explanation in
Figure 3--3 above proved to be too obscure, the user might say
EXPLAIN and have it expanded out in complete detail.  He might also say
EXPLAIN 2, to have it expanded out in steps roughly half as big as in
Figure 3--3 (the argument has the same meaning for both the WHY
and EXPLAIN commands).

\sectionskip
\sectionbegin[7]{More sophisticated HOWs}
        Previous examples have demonstrated that HOW questions can have a
range of possible meanings, depending on the referent of the question.
Examples above showed its use in determining how the value of an attribute was
reached and how different rules had been (or might be) used.  A more
complex situation arises if the question refers to a clause from a premise
of a rule, as in:

\null
{\tracebegin
Is\ the\ patient's\ illness\ with\ ORGANISM-1\ a\ hospital-acquired\eol
infection?\eol
**\ {\bf\ WHY}\eol
[i.e.,\ WHY\ is\ it\ important\ to\ determine\ whether\ or\ not\ the\ \eol
\ infection\ with\ ORGANISM-1\ was\ acquired\ while\ the\ patient\eol
\ was\ hospitalized?]\eol
\eol
[2.0]\ This\ will\ aid\ in\ determining\ the\ category\ of\eol
\ \ \ \ \ \ ORGANISM-1.\ \ It\ has\ already\ been\ established\ that\eol
\ [2.1]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg,\ and\eol
\ [2.2]\ the\ morphology\ of\ ORGANISM-1\ is\ rod,\ and\eol
\ [2.3]\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\ \ \ \ \ \ Therefore,\ if\eol
\ [2.4]\ the\ infection\ with\ ORGANISM-1\ was\ not\ acquired\ while\eol
\ \ \ \ \ \ \ the\ patient\ was\ hospitalized\eol
\ \ \ \ \ \ then\eol
\ there\ is\ strongly\ suggestive\ evidence\ (.8)\ that\ the\eol
\ categorey\ of\ ORGANISM-1\ is\ enterobacteriaceae\eol
\ [ALSO:\ there\ is\ weakly\ suggestive\ evidence\ (.1)\ that\ the\eol
\ \ identity\ of\ ORGANISM-1\ is\ pseudomonas-aeruginosa]\eol
\ [RULE037]\eol
\eol
**\ {\bf\ HOW\ [2.3]}\eol
[i.e.,\ HOW\ was\ it\ established\ that\ the\ aerobicity\ of\eol
\ ORGANISM-1\ is\ facultative?]\eol
\eol
The\ following\ were\ used:\eol
\ [3.1]\ RULE027\ indicated\ there\ is\ strongly\ suggestive\eol
\ \ \ \ \ \ \ evidence\ (.8)\ that\ the\ aerobicity\ of\ ORGANISM-1\ is\eol
\ \ \ \ \ \ \ facultative\eol
\ [3.2]\ RULE033\ indicated\ there\ is\ weakly\ suggestive\ evidence\eol
\ \ \ \ \ \ \ (.2)\ that\ the\ aerobicity\ of\ ORGANISM-1\ is\ not\eol
\ \ \ \ \ \ \ facultative.\eol
\eol
Since\ this\ gave\ a\ cumulative\ CF\ of\ (.6)\ for\ facultative,\ the\eol
evidence\ indicates\ that\ the\ aerobicity\ of\ ORGANISM-1\ is\eol
facultative.\eol

\traceend}
\figtitle 3-4{}

       To answer the  question about aerobicity
accurately, we must determine from the
execution trace the subset of rules that actually contributed to the conclusion
mentioned in clause [2.3]. In this case it is straightforward, since the set of
all rules invoked about aerobicity is available from the execution trace and the
appropriate subset (those that concluded that aerobicity was facultative) can be
determined  using the template mechanism to examine the conclusion of each of
them.

        A second example, from a different consultation, shows a more complex
response.

\null
{\tracebegin
Is\ PATIENT-1\ immunosuppressed\ or\ immunodeficient?\eol
** {\bf WHY}\eol
[i.e.,\ Why\ is\ it\ important\ to\ determine\ if\ the\ patient\ is\eol
\ immunosuppressed\ or\ immunodeficient?]\eol
\eol
[5.0]\ This\ will\ aid\ in\ determining\ the\ category\ of\eol
\ \ \ \ \ \ ORGANISM-1.\ \ It\ has\ already\ been\ established\ that\eol
\ [5.1]\ the\ site\ of\ CULTURE-1\ is\ blood,\ and\eol
\ [5.2]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg,\ and\eol
\ [5.3]\ the\ morphology\ of\ ORGANISM-1\ is\ rod,\eol
\ \ \ \ \ \ Therefore,\ if\eol
\ [5.4]\ the\ patient\ is\ immunosuppressed\ or\ immunodeficient,\eol
\ \ \ \ \ \ then\eol
\ there\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ category\eol
\ of\ ORGANISM-1\ is\ enterobacteriaceae\eol
\ [RULE085]\eol
\eol
**{\bf WHY}\eol
[i.e.,\ Why\ is\ it\ important\ to\ determine\ the\ category\ of\eol
\ ORGANISM-1?]\eol
\eol
[6.0]\ This\ will\ aid\ in\ determining\ the\ identity\ of\eol
\ \ \ \ \ \ ORGANISM-1.\ \ It\ has\ already\ been\ established\ that\eol
\ [6.1]\ the\ site\ of\ CULTURE-1\ is\ blood,\ and\eol
\ [6.2]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg,\ and\eol
\ [6.3]\ the\ morphology\ of\ ORGANISM-1\ is\ rod,\eol
\ \ \ \ \ \ Therefore,\ if\eol
\ [6.4]\ the\ category\ of\ ORGANISM-1\ is\ not\ known\ with\ certainty,\eol
\ \ \ \ \ \ then\eol
\ there\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ identity\eol
\ of\ ORGANISM-1\ is\ proteus.\eol
\ [RULE093]\eol
\eol
** {\bf HOW [6.4]}\eol
[i.e.,\ How\ will\ it\ be\ established\ that\ the\ category\ of\eol
\ ORGANISM-1\ is\ known,\ but\ not\ with\ certainty?]\eol
\eol
[7.0]\ Currently\ RULE085\ is\ being\ used.\eol
\ \ \ \ \ \ In\ addition,\ the\ following\ was\ also\ used:\eol
\ [7.1]\ RULE084\ indicated\ that\ there\ is\ strongly\ suggestive\eol
\ \ \ \ \ \ \ evidence\ (.8)\ that\ the\ category\ of\ the\ organism\ is\eol
\ \ \ \ \ \ \ enterobacteriaceae.\eol
\ \ \ \ \ \ Based\ on\ current\ patient\ data,\ the\ following\ may\ also\eol
\ \ \ \ \ \ prove\ useful\ later\ in\ the\ consultation:\eol
\ [7.2]\ RULE176\eol
\ [7.3]\ RULE021\eol
\eol
If,\ after\ trying\ these\ rules,\ the\ cumulative\ CF\ of\ any\ value\eol
of\ the\ category\ of\ ORGANISM-1\ is\ equal\ to\ or\ greater\ than\ .2\eol
and\ less\ than\ 1.0,\ it\ will\ be\ established\ that\ the\ category\eol
of\ ORGANISM-1\ is\ known,\ but\ not\ with\ certainty.\eol

\traceend}

\figtitle 3-5{}

      In this case the performance program has not yet finished determining the
organism's identity, and the user has asked how the process will establish
the answer with the indicated range of certainty.  Several sources of
information are required to provide an accurate and informative response.
First, {\TEIRESIAS} needs some indication of the ``meaning'' of the predicate
function ``known, but not with certainty.''

        There is a simple framework in which all of the predicate functions
can be viewed, and which provides the basis for our representation of this
information.  Each function can be seen as some segment of the number line
[-1.0, 1.0] that defines the range of certainty factors (several examples
are indicated in Figure 3--9 below, see [Shortliffe76] for the entire
list).  Associated with each predicate function is a numerical definition
in these terms.

% .STARTFIG;
% .BOXFIG;
%           [  ←∂    NOTSAME    ∂→  ]
% 
%                                   ( ←∂   SAME  ∂→ ]
% 
%                                   [← NOTDEFINITE →)
% 
%           ε∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂β∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂λ
% 
%         -1.0            -.2   0  .2              1.0
% 
% 
% [ -- closed interval
% ( -- open interval
% .WIDECAPFIG(Predicate functions:  Segments of the number line,NUMLINE:);
% .ENDFIG
% .continue

\topinsert{\vskip 18pc
\figtitle 3-6{Predicate functions:  Segments of the number line.}}

\noindent
For {\tt NOTDEFINITE} (the predicate function used in
clause [6.4]), the definition is $$\ctrline{(AND (GTE CF .2) (LT CF 1.0))}$$
Since experience has shown that the ``canned'' English phrases associated
with the predicate functions are often unclear, {\TEIRESIAS} prints the interval
definition at the end of the explanation.  This makes clear to the user the
criterion used to judge the truth or falsity of a clause.  In the current
case, for example, it is judged to be true that ``{\tt the category of
ORGANISM-1 is not known with certainty}'' if some value has been established
for it with a CF greater than or equal to .2 and less than 1.0.

\index{focus, in explanation);}The set of answers obtained by the
user during the consultation is
the second major source of information.  This set makes possible a
well-constrained list of rules that ``{\tt may prove useful later in the
consultation}'' (as in [7.2] and [7.3] above).  The entire list of rules
about identity is available internally; the subset of them yet to be
invoked can be determined by reference to the execution trace.  The premise\index{partial evaluation}
of each of these is checked (using the partial evaluation technique
discussed in chapter 2), disqualifying those that are known to be false
based on currently available information.  This helps {\TEIRESIAS} keep the answer
brief and avoid leading the user down a path in the reasoning tree known to
be a dead end.

        The major contribution of these various sources of information is
to allow {\TEIRESIAS} to construct explanations that are as sharply focused, precise,
and informative as possible.  The system's ability to constrain the set of
rules considered means that the user will not be inundated by large numbers
of possible paths, even when there are quite a few rules in the knowledge
base.  The system's ability to present some indication of the definition
of the predicate functions means that it can be terse in its normal
translation of a rule and still give the user some idea of the less obvious
aspects of the model of confirmation.

\sectionskip
\sectionbegin[8]{Special purpose responses}
	The goal-tree framework accounts for a very large part of
{\sc MYCIN}'s performance, but not all of it.  In order to meet the
primary design goal of accuracy, it was necessary to implement a small
number of special purpose responses in {\TEIRESIAS}'s explanation program.

	The description of the control structure in chapter 2 noted that
each object (a patient, culture, organism, etc.) has a number of its
associated attributes marked as ``primary'' and that these attributes are
automatically traced when the object is instantiated.\ffnote{This is in response
to the stylized presentation of information that is common in the domain:
A clinician is accustomed to offering certain standard pieces of information
about each topic.  Tracing the primary attributes of each object as soon as
the object is created means that the consultation presents a familiar
format.} Since this process is not part of the standard goal-tree search, a separate
mechanism is required to provide a response to a WHY inquiry at this point.
An example is shown below: It is a brief statement of fact, augmented by a
very simple form of generalization.\index{generalization}

% .STARTFIG;
% From what site was the specimen for CULTURE-1 taken?
% ** %3WHY%A
% 
% [\ie Why is it important to determine the site of CULTURE-1?]
% [8.0] There are 2 standard attributes that are important to 
%       determine in discussing a culture, and the site of the 
%       culture is one of them.
%         The site of CULTURE-1 may be useful later in the
%       consultation.  For example, it is very important in
%       determining the identity of an organism, and is
%       significant in determining whether or not an organism is
%       a contaminant.
% .ENDFIG;

\vskip 11pc
\figtitle 3-7{}

	This response takes account of the motivation for automatically tracing the
primary attributes: They are often the most informative pieces of
information about the problem.  In response, the explanation routines
examine the knowledge base to see how the answer may be used and select
the most common uses.  The piece of information originally requested is
then classified as being ``very important,'' ``significant,'' or ``relevant'' to
each of those uses, according to the number of rules found.  In the example
above, of all the rules which mention culture site in their premise, there
are a large number that conclude about organism identity and a smaller
number that conclude about possible contaminants.

	A second special purpose mechanism is employed to make sure that
implicit deductions do not confuse the user.  Consider a consultation in
which the user indicates that the culture site is blood. In printing out a
rule later on, the system might make reference to the fact that {\sl the site
of the culture is one of those sites that are normally sterile}.  If the
user asks how this fact was established, the program responds:

% .STARTFIG;
% [i.e. How was it established that the site of CULTURE-1 is 
%  one of those sites that are normally sterile?]
% 
% You said so [question 4].
% [Those sites that are normally sterile are: UPPER-GI, BLOOD, 
% BONE, BRAIN, CSF, LIVER, LOWER-RESP, PERICARDIUM, 
% PLEURAL-SPACE, SINUS.]
% .ENDFIG;
% .skip
% .continue

\topinsert{\vskip 10pc \figtitle 3-8{}}
\noindent
Since the user only said that the site was blood, and may not be aware of
exactly which sites are sterile, this additional information is made clear to
him.

\sectionskip
\sectionbegin[9]{Limitations}
	There are several sources of limitations in the approach we have
taken.

\subsectionbegin[9.1]{Restriction to a Single Framework}
	First, the choice of a single primitive operation (rule invocation)
and a single framework (the goal tree) restricts the class of events that
can be explained.  We have seen that behavior caused by mechanisms outside
this framework must either be explained with special purpose routines or
left unaccounted for.  In terms of the current performance program
({\sc MYCIN}), the most serious example of the latter is drug selection.  While
some part of that process is expressed in rules, much of the optimization
phase (minimizing the number of drugs and side effects  and maximizing
coverage) is in complex {\sc LISP} code and hence inaccessible to the
methods used in {\TEIRESIAS}.

	Two possible approaches to solving this are ({\it i\/}) put everything in
rules, or ({\it ii\/}) provide multiple frameworks.  Some preliminary steps toward
the former are discussed in chapter 7, which describes the use of
meta-rules to express many types of knowledge.  This appears to be only a\index{production rules}
partial solution, however.  While production rules are a general
computational mechanism, their utility as a representation for some tasks
is questionable (see [Davis77a] for a discussion of this issue).
Developing multiple frameworks appears to be a more general solution, but
has not yet been explored.

\subsectionbegin[9.2]{Lack of a General Model of Explanation}
	A more fundamental conceptual limitation arises out of the priorities
of our design criteria.  {\TEIRESIAS}'s explanation facilities do indeed supply an
effective tool for discovering the basis for the performance program's
behavior and for examining its knowledge base.  They do not, however, contain
a particularly sophisticated model of explanation.  This becomes evident in
several ways.  It was noted earlier, for instance, that ``why'' and ``how'' are
underspecified and must necessarily be
expanded by  {\TEIRESIAS} to avoid misinterpretation by
the user (\eg, ``Why'' might mean ``Why did you ask about that instead
of\ellipsis,'' or ``Why did you ask about that now,'' etc.).  These other
interpretations are valid questions about the system, yet there is no way
in the current framework to answer them.

	As another example, there are certain types of information that
are missing from the system entirely,  which are judged necessary if we are to
supply a truly comprehensive explanation capability.  Consider the
following example.

% .STARTFIG;
% Was the infection with ORGANISM-1 acquired while the patient
% was hospitalized?
% ** %3WHY%A
% [\ie Why is it important to determine if the infection with 
% ORGANISM-1 was acquired while the patient was hospitalized?]
% 
% [1.0] This will help to determine the identity of ORGANISM-1.
%       It has already been established that
%  [1.1] the gramstain of ORGANISM-1 is gramneg, and
%  [1.2] the morphology of ORGANISM-1 is rod, and
%  [1.3] the aerobicity of ORGANISM-1 is facultative,
%       Therefore, if
%  [1.4] the infection with ORGANISM-1 was acquired while the 
%        patient was hospitalized,
%       Then
%  there is weakly suggestive evidence (.2) that the identity of
%  the organism is pseudomonas.
%  [RULE050]
% .ENDFIG;CONTINUE;

\topinsert{\vskip 16pc \figtitle 3-9{}}
\noindent
A naive user might now be tempted to ask a different sort of ``why'':
{\sl Why is it true that a gram negative facultative rod in a hospital setting is
likely to be a pseudomonas?} The answer is that certain sorts of bacteria are
very common in the hospital environment, but there is currently no
representation of this in the system.  Since the sequence of ``why'' questions of
this sort can be continued indefinitely ({\sl Why are some bacteria more common in
the hospital?}, etc.), it is not unreasonable to cut off at some point.  But
currently the question cannot be answered even once, and in a more general
explanation model, this should be possible.

\index{information metric}The lack of a user model in the
information metric has been mentioned,
and this too is an important element.  In our current model, two rules with
the same certainty factor have the same information content, yet a user who
is familiar with only the first of them will find much more information in
the second.

\index{abstraction}Next, while our approach generates high-level explanations by
leaving out detail, there is another sort of abstraction that would be very
useful.  The system should be able to describe its actions at different
conceptual
levels, perhaps  at levels ranging from rule
invocation to {\sc LISP} interpretation, to function calls, etc.  A
limited form of this kind of ability is described in [Sacerdoti77], but
there it arises from code that has been intentionally structured in this
multilevel form.  More interesting would be an ability to generate such
explanations from an understanding of the process at each level.  Some of
the work on models of disease processes described in [Kulikowski73] may be
relevant here.

	Finally, there is the possibility of decoupling explanation from
control flow.  Section 3--2 pointed out a fundamental assumption
of our approach: that a recap of program actions can be a plausible
explanation.  This assumption need not be made and explanations could be
considered separately, distinct from execution (as in [Brown75]).  This is common
human behavior---the account someone gives of how he solved a complex
problem may be quite different from a simple review of his actions.  The
difference is often more than just leaving out the dead ends  or
omitting the details of the solution.  Solving the problem often
produces new insights and shows results in a totally different view, one which
often admits  a much more compact explanation.  There is greater
flexibility from an approach of this kind since it can be used to supply a wider
variety of explanations; but it also requires a new and separate basis for
generating explanations and, hence, is more difficult.

	All of these examples point the way to useful extensions to {\TEIRESIAS} that
would give it a far more general and powerful explanation capability.

\subsectionbegin[9.3]{Lack of Ability to Represent Control Structures}
	The third, and most relevant, limitation is the lack of
a substantive ability to represent control structures.  In the current system, the closest
approximation comes from the use of the goal-tree framework as a model of the
control structure.  But this ``model'' exists only implicitly, expressed by the
organization of code in the explanation facility rather than as a separate
entity.  Shortcomings are evidenced by the fact that almost any alteration of
the control structure of the performance program requires an analogous recoding
of {\TEIRESIAS}'s explanation routines.  If there were instead some representation of the
control structure that the explanation routines could examine, the system would
be much more flexible.  The general scheme would be as pictured below:

% .STARTFIG;
% .BOXFIG;
% 
% ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃     ⊂∂∂∂∂∂∂∂∂∂∂∂⊃     ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% }representation}     } execution }     }  knowledge of what  }
% }of control    }     }   trace   }     }     constitutes     }
% }structure     }     α%∂∂∂∂∂∂∂∂∂∂∂$     }   an explanation    }
% α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂$∂ ⊃  	    }	     ⊂ ∂α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 
% 		  }        }        }
% 
% 		  ↓        ↓        ↓
% 		  ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% 		  }   explanation   }
% 		  }    generator    }
% 		  α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% 			   |
% 			   ↓
% 	    explanation of program behavior
% .FIG(A more sophisticated explanation-generation scheme);
% 
% .ENDFIG;CONTINUE;

\vskip 11pc
\figtitle 3-{10}{A more sophisticated explanation-generation scheme.}
\noindent
Given some representation of the control structure and a body of knowledge
about what an explanation is, {\TEIRESIAS} would generate a comprehensible account of
performance program behavior.  Supplying either of these seems to be a
formidable but interesting prospect.

The fact that a programmer can scan a strange piece of code and then
explain the behavior of a program executing it, suggests that the task is at
least plausible.  Formalizing the knowledge of what it means to ``explain''
does not seem to have received extensive attention.  Some of the work on
affects and intensions by [Faught74] may be relevant, as may be the conceptual
dependency work in [Reiger74] and the work on computer-aided instruction
in [Brown75].

	Some small steps toward representing the control structure in an
accessible form are described in chapter 7.  There we explore the use of
meta-rules to express certain aspects of the performance program's control
structure, and hence render them accessible to the current explanation
mechanism.

	A more sophisticated form of representation is needed, however.
The source code of a program is not a particularly good choice for two
reasons.  First, it carries too much implementation detail.  It may be
useful to know only that a piece of code is, for instance, an iterative
loop, and the detail of how it is implemented often only confuses the
issue.  Second, it carries too little intentional information.  
{\sc LISP}'s {\tt CAR} operation, for example, can usually be read as 
{\sl first element} of a list; but inside a loop, it might be more appropriately
viewed as {\sl next element}.

	The task requires some way of suppressing implementation detail and
emphasizing intentions.  There is a common style of programming that\index{extended data type}
accomplishes some of this.  It emphasizes the use of extended data types
(\eg, record structures) and macros (or functions) designed for the task
at hand.  It may include two functions called {\tt FIRST} and {\tt NEXT}, for
instance, even though both perform the same {\tt CAR} operation.  Something
along this line has been suggested in [Hewitt71], but the emphasis there
is on program correctness and automatic programming.  The point here is
simply to give the programmer a way of expressing his (perhaps informal)
intentions for each section of code so that the program can later be
explained.  Note that these intentions might include not only descriptions
of control structure but might go on to specify many other things about
the code: design considerations, algorithm choices, and perhaps other kinds
of information of the sort found in well-written documentation.  Thus, where
the efforts in program correctness have concentrated on describing
precisely ``what'' a program should do, intentional information might include
descriptions of the ``how'' of program design.  The work in [Goldstein74]
suggests the multiple uses that might be made of such annotations: That
system based its debugging of simple programs on an understanding of common
error types plus remarks in the code that indicated the programmer's
``plan'' for solving the problem.

	Flowcharts are a second possibility; some text-oriented
representation of them might prove useful.  In an analogy to some of the
work on program correctness, they might be annotated with ``motivation
conditions,'' providing, thereby, both a representation of the control
structure and the information necessary to explain it.  Both of these are
clearly very speculative; there is much room for additional work.

\subsectionbegin[9.4]{Other Communication Media}
	We have not yet explored any graphics-oriented explanations, but
Figure 3--1 illustrates that they might be very useful.  The tree shown
there makes  clear what otherwise takes many lines of text.
Considering the natural interpretation of the performance program's control
structure in graphic form and the desire to be as brief as possible, it
appears to be an excellent medium.

\sectionskip
\lsectionbegin[10]2{Trace of System Performance:}{Explanations for System Debugging}

\epigraph{And you are wrong if you believe that one.}
\author{Sophocles}
\source{Oedipus the King, line 554}
\epigraphend

\noindent
Work on giving a program the ability to explain its actions
([Shortliffe75a]) was originally motivated by concerns about
comprehensibility:  Consultation programs are unlikely to be accepted by
users if they function as ``black boxes'' that simply print their final
answers.  Much of the work described earlier in this chapter is in the same
vein.

	But there is another, different, and very useful application of
explanation: program debugging, in particular as a means of setting an
appropriate context for knowledge acquisition.  As an introduction to
the knowledge acquisition sections that follow, an example below
demonstrates how the explanation routines in {\TEIRESIAS} have been designed to allow
the domain expert to track down the source of an error in the knowledge
base.

	One of the options available to the expert is having the system
stop after it has presented its diagnosis, to give him a chance to comment
on it.  This pause provides a natural starting place for evaluation and
debugging.  Once the bug is found, the acquisition session, described in
later chapters, then goes on to repair the problem by teaching the system
the new rule.

	The example presented here will be carried on through the knowledge
acquisition chapters and developed in detail.  In order to present a
single example that would include all the features to be displayed, it was
necessary to create a bug by removing a rule from the performance program's
knowledge base and eliminating all references to it.  The example is
special in no other sense, however, and with the obvious exceptions of font
changes, annotations, and slight reformatting, the interaction appears just
as it does here.  For completeness, the entire consultation is presented
below. 

\null
{\tracebegin
MYCIN\ \ 24-NOV-76\ ...\eol
\eol
Special\ options\ (type\ ?\ for\ help):\eol
**\ {\bf RD\ SAVE}\eol
Hello,\ Dr.\ Davis\eol
\traceend}
\scomm
{The expert identifies himself to the system and indicates that he wants
a record of this consultation kept in the case library.}
\ecomm
{\tracebegin
\eol
This\ will\ be\ patient\ 281.\eol
If\ you\ would\ care\ to\ enter\ a\ brief\ clinical\ summary\ of\ your\eol
patient's\ case,\ to\ be\ used\ for\ easy\ future\ reference\ to\ this\eol
file,\ please\ do\ so\ now\ (type\ as\ many\ lines\ as\ required,\eol
terminate\ with\ a\ blank\ line):\eol
\eol
**{\bf CLASSIC\ CASE\ OF\ GRAM\ NEGATIVE\ ROD\ INFECTION\ FOR\ A\ }\eol
**{\bf PATIENT\ WITH\ A\ NON-NOSOCOMIAL\ DISEASE}\eol
**\eol
\eol
--------PATIENT-281--------\eol
1)\ Patient's\ name:\ (first-last)\eol
**\ {\bf ALBERT\ HALL}\eol
2)\ Sex:\eol
**\ {\bf MALE}\eol
3)\ Age:\eol
**\ {\bf 34}\eol
4)\ Have\ you\ been\ able\ to\ obtain\ positive\ microbiological\eol
\ \ \ information\ about\ a\ possible\ infection\ of\ Albert\ Hall?\eol
**\ {\bf YES}\eol
\eol
\ --------INFECTION-1--------\eol
\ 5)\ What\ is\ the\ infection?\eol
\ **\ {\bf PRIMARY-BACTEREMIA}\eol
\ 6)\ Please\ give\ the\ date\ and\ time\ when\ signs\ or\ symptoms\ of\eol
\ \ \ \ the\ primary-bacteremia\ (INFECTION-1)\ first\ appeared.\eol
\ **\ {\bf 15\ DECEMBER\ 77\ 12:00}\eol
\ The\ most\ recent\ culture\ yielding\ positive\ microbiological\eol
\ information\ \ about\ the\ primary-bacteremia\ (INFECTION-1)\ will\eol
\ be\ referred\ to\ as:\eol
\eol
\ \ --------CULTURE-1--------\eol
\ \ 7)\ From\ what\ site\ was\ the\ specimen\ for\ CULTURE-1\ taken?\eol
\ \ **\ {\bf BLOOD}\eol
\ \ 8)\ Please\ give\ the\ date\ and\ time\ when\ this\ blood\ culture\eol
\ \ \ \ \ (CULTURE-1)\ was\ obtained.\ (mo/da/yr\ time)\eol
\ \ **\ {\bf 16\ DECEMBER\ 77\ 12:00}\eol
\ \ The\ first\ significant\ organism\ from\ this\ blood\ culture\eol
\ \ (CULTURE-1)\ will\ be\ referred\ to\ as:\eol
\eol
\ \ \ --------ORGANISM-1--------\eol
\ \ \ 9)\ Enter\ the\ identity\ of\ ORGANISM-1:\eol
\ \ \ **\ {\bf UNKNOWN}\eol
\ \ \ 10)\ Is\ ORGANISM-1\ a\ rod\ or\ coccus\ (etc.):\eol
\ \ \ **\ {\bf ROD}\eol
\ \ \ 11)\ The\ gram\ stain\ of\ ORGANISM-1:\eol
\ \ \ **\ {\bf GRAMNEG}\eol
\ \ \ 12)\ Did\ ORGANISM-1\ grow\ in\ the\ aerobic\ bottle?\eol
\ \ \ **\ {\bf YES}\eol
\ \ \ 13)\ Did\ ORGANISM-1\ grow\ in\ the\ anaerobic\ bottle?\eol
\ \ \ **\ {\bf YES}\eol
\ \ \ 14)\ Is\ the\ patient's\ illness\ with\ ORGANISM-1\ a\ hospital-\eol
\ \ \ \ \ \ \ acquired\ infection?\eol
\ \ \ **\ {\bf NO}\eol
\ \ \ 15)\ Have\ there\ been\ POSITIVE\ cultures\ yielding\ organisms\eol
\ \ \ \ \ \ \ about\ which\ you\ will\ NOT\ be\ seeking\ advice?\eol
\ \ \ **\ {\bf NO}\eol
\ \ \ 16)\ Is\ Albert\ Hall\ a\ burn\ patient?\eol
\ \ \ **\ {\bf NO}\eol
\ \ \ 17)\ Do\ you\ consider\ Albert\ Hall\ to\ be\ a\ compromised\ host\eol
\ \ \ \ \ \ \ (alcoholic,\ immunosuppressed,\ etc.)?\eol
\ \ \ **\ {\bf NO}\eol
\ \ \ 18)\ What\ is\ the\ suspected\ portal\ of\ entry\ of\ ORGANISM-1\eol
\ \ \ \ \ \ \ into\ this\ sterile\ site?\eol
\ \ \ **\ {\bf GI}\eol
\ \ \ 19)\ Has\ Albert\ Hall\ had\ any\ G-U\ surgery\ or\ manipulation\ of\eol
\ \ \ \ \ \ \ the\ urinary\ tract\ (eg.\ catheter,\ cystoscopy,\ etc.)?\eol
\ \ \ **\ {\bf NO}\eol
\ \ \ 20)\ Including\ this\ blood\ culture\ (CULTURE-1),\ how\ many\ times\eol
\ \ \ \ \ \ \ during\ this\ series\ of\ cultures\ was\ this\ site\ cultured?\eol
\ \ \ **\ {\bf 3}\eol
\ \ \ 21)\ In\ this\ series,\ how\ many\ of\ the\ cultures\ from\ this\eol
\ \ \ \ \ \ \ site\ were\ positive\ for\ ORGANISM-1?\eol
\ \ \ **\ {\bf 3}\eol
\ \ 22)\ Any\ other\ significant\ organisms\ isolated\ from\ this\ blood\eol
\ \ \ \ \ \ culture\ (CULTURE-1)?\eol
\ \ **\ {\bf NO}\eol
\ 23)\ Did\ any\ additional\ cultures\ yield\ positive\ microbiological\eol
\ \ \ \ \ information\ which\ you\ believe\ is\ associated\ with\ the\eol
\ \ \ \ \ primary-bacteremia\ (INFECTION-1)?\eol
\ **\ {\bf NO}\eol
24)\ Does\ Albert\ Hall\ have\ any\ other\ infection\ about\ which\ you\eol
\ \ \ \ have\ obtained\ positive\ microbiological\ information?\eol
**\ {\bf NO}\eol
25)\ Do\ you\ suspect\ an\ infection\ at\ a\ site\ which\ you\ have\ been\eol
\ \ \ \ unable\ to\ culture,\ or\ from\ which\ all\ cultures\ were\eol
\ \ \ \ negative?\eol
**\ {\bf NO}\eol
26)\ Is\ Albert\ Hall\ currently\ receiving\ therapy\ with\ any\eol
\ \ \ \ antimicrobial\ agent?\eol
**\ {\bf NO}\eol
27)\ During\ the\ present\ illness,\ has\ Albert\ Hall\ been\ treated\eol
\ \ \ \ with\ an\ antimicrobial\ agent\ which\ is\ no\ longer\ being\eol
\ \ \ \ administered?\eol
**\ {\bf NO}\eol
\eol
My\ therapy\ recommendation\ will\ be\ based\ on\ the\ following\eol
probable\ infection(s)\ and\ potential\ causative\ organism(s):\eol
\eol
INFECTION-1\ is\ PRIMARY-BACTEREMIA\eol
\eol
\ \ \ \ <Item\ 1>\ \ E.COLI\ [ORGANISM-1]\eol
\ \ \ \ <Item\ 2>\ \ PSEUDOMONAS-AERUGINOSA\ [ORGANISM-1]\eol
\eol
\eol
Are\ all\ these\ identities\ correct?\eol
++**\ {\bf N}\eol
\traceend}
\scomm
{At this point {\TEIRESIAS} steps in, asks for the expert's opinion, and is told that
something is wrong.  From here on, the interaction is between the expert
and {\TEIRESIAS}, with the performance program in the background being manipulated by
{\TEIRESIAS}}.
\ecomm
{\tracebegin
\eol
Are\ there\ any\ identities\ missing?\eol
++**\ {\bf Y}\eol
Which\ one(s)?\eol
++**\ {\bf KLEBSIELLA-PNEUMONIAE\ PROTEUS-NON-MIRABILIS}\eol
Are\ there\ any\ identities\ that\ shouldn't\ have\ appeared?\eol
++**\ {\bf Y}\eol
Which\ one(s)?\eol
++**\ {\bf PSEUDOMONAS-AERUGINOSA}\eol
\eol
We'll\ start\ with\ the\ PSEUDOMONAS-AERUGINOSA\ first.\eol
\traceend}
\scomm
{Heuristics derived from our experience in debugging are built into the
system.  They suggest that the best approach is (a) to track down one
problem at a time, and (b) to start with an answer that shouldn't have
appeared, if there is one.  Experience has suggested that values which
appear inappropriately are often the result of a bug causing several
problems; so curing one often removes a number of problems at once.}
\ecomm
{\tracebegin
\eol
Do\ you\ want\ to\eol
\ \ \ \ \ \ 1]\ track\ down\ the\ problem\ yourself,\ or\eol
\ \ \ \ \ \ 2]\ allow\ me\ to\ guide\ the\ debugging,\ or\eol
\ \ \ \ \ \ 3]\ ignore\ it\ for\ now\ and\ fix\ it\ another\ time?\eol
Type\ 1,\ 2\ or\ 3\eol
++**\ {\bf 1}\eol
\traceend}
\scomm
{The\ first option allows the expert to use all the standard explanation
facilities and will be demonstrated here.  The second is based on an
analysis of the control structure that drives the consultation and is\index{human engineering}
explored in the next chapter.  The final option is for human engineering
purposes and allows the expert to sidestep the whole process if he should
decide to do so.}
\ecomm
{\tracebegin
\eol
The\ following\ rules\ were\ used\ in\ deducing\ that\ the\ identity\ of\eol
\ \ \ \ \ \ \ \ \ \ ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
RULE184\eol
-------\eol
Since\ [1.1]\ the\ category\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ \ \ \ [1.2]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg\eol
\ \ \ \ \ \ [1.3]\ the\ morphology\ of\ ORGANISM-1\ is\ rod\eol
\ \ \ \ \ \ [1.4]\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\eol
\ There\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ identity\ of\eol
\ \ \ \ \ \ \ \ \ ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
Now\ use\ the\ standard\ explanation\ commands\ (WHY\ HOW,\ etc.)\ to\eol
find\ the\ bug.\ \ When\ you've\ discovered\ what\ you\ think\ the\eol
problem\ is,\ type\ ``OK'',\ and\ we\ can\ try\ to\ fix\ it\eol
\eol
\ \ \ \ \ \ **\ {\bf HOW [1.1]}\eol
\eol
[i.e.\ HOW\ was\ it\ established\ that\ the\ category\ of\ ORGANISM-1\eol
\ is\ not\ known?]\eol
\eol
There\ were\ no\ rules\ successfully\ invoked\ to\ deduce\ the\ category\eol
of\ ORGANISM-1.\ \ The\ following\ rules\ failed:\eol
\ \ \ \ \ \ [2.1]\ RULE050\eol
\ \ \ \ \ \ [2.2]\ RULE116\eol
\traceend}
\scomm
{When the expert is tracking down a bug, the answer to a ``how'' question
includes an indication of rules that might have been executed but which
failed.  This is not normally useful to the average observer and so is
omitted in other circumstances.}
\ecomm
{\tracebegin
\eol
\ \ \ \ \ **\ {\bf HOW\ [2.1]}\eol
\eol
It\ was\ established\ that\eol
\ \ \ \ \ \ [3.1]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg,\ and\eol
\ \ \ \ \ \ [3.2]\ the\ morphology\ of\ ORGANISM-1\ is\ rod,\ and\eol
\ \ \ \ \ \ [3.3]\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
But\ it\ was\ never\ established\ that\eol
\ \ \ \ \ \ [3.4]\ the\ infection\ with\ ORGANISM-1\ was\ acquired\ while\eol
\ \ \ \ \ \ \ \ \ \ \ \ the\ patient\ was\ hospitalized\eol
[And\ the\ conclusion\ could\ not\ be\ made\ that\eol
\ there\ is\ strongly\ suggestive\ evidence\ (.7)\ that\ the\ category\eol
\ of\ ORGANISM-1\ is\ enterobacteriaceae]\eol
[RULE050]\eol
\eol
\eol
\ \ \ \ **\ {\bf HOW\ [2.2]}\eol
\eol
It\ was\ established\ that\eol
\ \ \ \ \ \ [4.1]\ the\ identity\ of\ the\ organism\ is\ not\ known,\eol
But\ it\ was\ never\ established\ that\eol
\ \ \ \ \ \ [4.2]\ the\ gram\ stain\ of\ the\ organism\ is\ not\ known,\eol
\ \ \ \ \ \ [4.3]\ the\ morphology\ of\ the\ organism\ is\ not\ known,\ and\eol
\ \ \ \ \ \ [4.4]\ the\ site\ of\ the\ culture\ is\ csf,\ and\eol
\ \ \ \ \ \ [4.5]\ the\ infection\ is\ meningitis,\ and\eol
\ \ \ \ \ \ [4.6]\ the\ age\ (in\ years)\ of\ the\ patient\ is\ less\ than\ or\eol
\ \ \ \ \ \ \ \ \ \ \ \ equal\ to\ .17\eol
[And\ the\ conclusion\ could\ not\ be\ made\ that\eol
\ there\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ category\eol
\ of\ ORGANISM-1\ is\ enterobacteriaceae]\eol
[RULE116]\eol
\eol
\ \ \ \ **\ {\bf OK}\eol
\eol
Good,\ now\ do\ you\ want\ to:\eol
\ \ \ 1]\ give\ me\ a\ new\ rule\eol
\ \ \ 2]\ modify\ an\ existing\ rule\eol
++**\ {\bf 1}\eol
\eol
The\ new\ rule\ will\ be\ called\ RULE383\eol
\ If:\ \ \ \ 1\ -\eol
\eol
\eol
\traceend}

        The expert has tracked down one problem: The performance program should
have been able to deduce the probable category of the organism.  {\TEIRESIAS} is now
ready to accept a new rule to fix the problem.  We're going to stop at this
point and start again in chapter 5 in order to see how the acquisition
process proceeds.

\sectionskip
\sectionbegin[11]{SUMMARY}
	Three different means of generating explanations have been explored
in this chapter.  The first technique, which explores branches of the tree
not yet traversed by the consultation program, is used in producing answers
to ``how'' questions (\eg, {\sl How will you determine the identity of 
ORGANISM-1?}).  These are produced by having the explanation program simulate
the operation of the consultation program via special-purpose software.  It
is thus a hand-crafted solution.
				
\index{goal tree}\index{tree traversal}More general is the use of the
goal-tree concept as a basis for
explanation.  Since the notion of a goal tree models a large part of the
control structure, it provides a single, uncomplicated model for much of
the performance program's behavior.  As a result, a simple formalism that
equates ``why'' and ``how'' with tree traversal offers a reasonably powerful
and comprehensive explanation capability.

	The most general technique involves having {\TEIRESIAS} directly examine
the rules in the knowledge base, as in the use of the templates to determine
whether a premise clause has already been established or is still untested.
In doing this, {\TEIRESIAS}'s explanation facility examines and interprets the same
piece of code that the performance program is about to execute.  The
resulting explanation is thus constructed with reference to the content of
the rule, and this referral is guided by information (the templates)
contained in the rule components themselves.  

	We have also seen two distinct uses for the explanations that {\TEIRESIAS} can
generate.  They can help make a performance program more comprehensible by
displaying the reasoning it employed and can aid in uncovering shortcomings
in the knowledge base.  The next three chapters follow up on this second
theme and show how to rectify the errors discovered.

\worldend